// Autumn 2012 TCSS343 Homework 3
// K-Way Mergesort
// Dallas Rosson

import java.util.PriorityQueue;

/**
 * A class that contains a group of sorting algorithms. The input to the sorting
 * algorithms is assumed to be an array of integers.
 * 
 * @author Donald Chinn
 * @author Daniel M. Zimmerman
 * @author Dallas Rosson
 * @version October 2012
 */
public final class Sort
{
  /**
   * Reused text constant.
   */
  private static final String FIVE_SPACES = "     ";
  
  /**
   * Reused text constant.
   */
  private static final String BRACKET_EQUALS = "] = ";
    
  /**
   * The run time.
   */
  private static int my_time = 0;

  /**
   * The k variable.
   */
  private static int my_k = 0;
  
  /**
   * The input size.
   */
  private static int my_n = 0;

  
  /**
   * Private constructor to prevent instantiation.
   */
  private Sort()
  {
    // don't do anything
  }

  /**
   * Given an array of integers and an integer k, sort the array (ascending
   * order) using k-way mergesort.
   * 
   * @param the_data An array of integers.
   * @param the_k The k in k-way mergesort.
   */
  public static void kwayMergesort(final int[] the_data, final int the_k)
  {
    kwayMergesortRecursive(the_data, 0, the_data.length - 1, the_k);
  }

  /**
   * The recursive part of k-way mergesort. Given an array of integers (data), a
   * low index, high index, and an integer k, sort the subarray data[low..high]
   * (ascending order) using k-way mergesort.
   * 
   * @param the_data An array of integers.
   * @param the_low The low index.
   * @param the_high The high index.
   * @param the_k The k in k-way mergesort.
   */
  public static void kwayMergesortRecursive(final int[] the_data, 
                                            final int the_low, final int the_high,
                                            final int the_k)
  {
    if (the_low < the_high)
    {
      for (int i = 0; i < the_k; i++)
      {
        kwayMergesortRecursive(the_data, 
                               the_low + i * (the_high - the_low + 1) / the_k, 
                               the_low + (i + 1) * (the_high - the_low + 1) / the_k - 1,
                               the_k);
      }
      merge(the_data, the_low, the_high, the_k);
    }
  }

  /**
   * Given an array of integers (data), a low index, a high index, and an
   * integer k, sort the subarray data[low..high]. This method assumes that each
   * of the k subarrays data[low + i*(high-low+1)/k .. low + (i+1)*(high-low+1)/k - 1], 
   * for i = 0..k-1, are sorted.
   * 
   * @param the_data An array of integers.
   * @param the_low The low index.
   * @param the_high The high index.
   * @param the_k The k in k-way mergesort.
   */
  public static void merge(final int[] the_data, 
                           final int the_low, final int the_high, 
                           final int the_k)
  {
    if (the_high < the_low + the_k)
    {
      // the subarray has k or fewer elements, 
      // so just make one big heap and do deleteMins on it
      final PriorityQueue<MergesortHeapNode> heap = 
          new PriorityQueue<MergesortHeapNode>();
      for (int j = the_low; j <= the_high; j++)
      {
        heap.add(new MergesortHeapNode(the_data[j], 0));
      }
      for (int j = the_low; j <= the_high; j++)
      {
        try
        {
          the_data[j] = heap.remove().data();
        }
        catch (final IllegalStateException e)
        {
          System.out.println("Tried to delete from an empty heap.");
        }
      }
    }
    else
    {
      // divide the array into k subarrays and do a k-way merge
      
      // How long the data is.
      int length = the_high - the_low + 1;
      
      // Index arrays.
      final int[] maxIndex = new int[the_k];
      final int[] curIndex = new int[the_k];
      
      // The sorted elements.
      final int[] sortedElements = new int[length];
      
      // The queue.
      final PriorityQueue<MergesortHeapNode> sortingQueue = new PriorityQueue<MergesortHeapNode>();
            
      
      for (int i = 0; i < the_k; i++) {
        // Copied from above method so that the indexing would be the same.
        curIndex[i] = the_low + i * length / the_k;
        maxIndex[i] = the_low + (i + 1) * length / the_k - 1;
        
        // Puts the head node into the queue.
        sortingQueue.offer(new MergesortHeapNode(the_data[curIndex[i]], i));
      }
      
      for (int i = 0; i < length; i++) {
        
        
        // Removes the head node and places it in the sorted elements array.
        final MergesortHeapNode current = sortingQueue.remove();
        sortedElements[i] = current.data();
        final int curSubArray = current.subarray();
        
        if (curIndex[curSubArray] < maxIndex[curSubArray]) {
          curIndex[curSubArray] = curIndex[curSubArray] + 1;
          sortingQueue.offer(new MergesortHeapNode(the_data[curIndex[curSubArray]], curSubArray));
          
        }
      }
      
      System.arraycopy(sortedElements, 0, the_data, the_low, length);
    }
  }

  /**
   * Given integer the_size, produce an array of the_size random integers. The
   * integers of the array are between 0 and the_size (inclusive) with random
   * uniform distribution.
   * 
   * @param the_size The number of elements in the returned array.
   * @return an array of the_size randomly generated integers.
   */
  public static int[] getRandomArrayOfIntegers(final int the_size)
  {
    final int[] data = new int[the_size];
    for (int i = 0; i < the_size; i++)
    {
      data[i] = (int) ((the_size + 1) * Math.random());
    }
    return data;
  }

  /**
   * Given an integer the_size, produce an array of the_size random integers. The
   * integers of the output array are between 0 and the_size-1 with exactly one of
   * each in the array. Each permutation is generated with random uniform
   * distribution.
   * 
   * @param the_size The number of elements in the returned array.
   * @return an array of integers.
   */
  public static int[] getRandomPermutationOfIntegers(final int the_size)
  {
    final int[] data = new int[the_size];
    for (int i = 0; i < the_size; i++)
    {
      data[i] = i;
    }
    // shuffle the array
    for (int i = 0; i < the_size; i++)
    {
      int temp;
      final int swap = i + (int) ((the_size - i) * Math.random());
      temp = data[i];
      data[i] = data[swap];
      data[swap] = temp;
    }
    return data;
  }

  /**
   * Perform checks to see if the algorithm has a bug.
   */
  private static void correctnessTest()
  {
    final int[] data = getRandomPermutationOfIntegers(100);

    for (int i = 0; i < data.length; i++)
    {
      System.out.println("data[" + i + BRACKET_EQUALS + data[i]);
    }

    final int k = 1000;
    kwayMergesort(data, k);

    // verify that data[i] = i
    boolean error = false;
    for (int i = 0; i < data.length; i++)
    {
      if (data[i] != i)
      {
        error = true;
        System.out.println("Error!  data[" + i + BRACKET_EQUALS + data[i] + ".");
      }
    }
    if (!error)
    {
      System.out.println("data was correctly sorted");
    }
  }

  /**
   * Perform timing experiments.
   */
  private static void timingTest()
  {
    /* ------ Modified to make testing easier ------ */
    
    // start the timer
    final long start_time = System.currentTimeMillis();
    
    final int[] data = getRandomArrayOfIntegers(my_n);
    kwayMergesort(data, my_k);

    // stop the timer
    final long finish_time = System.currentTimeMillis();
    final long total_time = finish_time - start_time;
    my_time = (int) total_time;

    System.out.println("** Results for k-way mergesort:");
    System.out.println(FIVE_SPACES + "n = " + my_n + FIVE_SPACES + "k = " + my_k);
    System.out.println(FIVE_SPACES + "Time: " + total_time + " ms.");
  }
  
//Getters and Setters.
  
 /**
  * Sets the k value in a k-way mergesort.
  * 
  * @param the_k to set.
  * <br>the_k must be >= 0.
  */
 public static void setK(final int the_k) 
 {
   
   if (the_k >= 0) 
   {
     
     my_k = the_k;
     
   } 
   else 
   {
     
     my_k = 0;
   }
 }
 
 /**
  * Sets the input size.
  * 
  * @param the_n to set.
  * <br>the_n must be >= 1.
  */
 public static void setN(final int the_n) 
 {
   
   if (the_n >= 1) 
   {
     
     my_n = the_n;
     
   } 
   else 
   {
     
     my_n = 1;
   }
 }

 /**
  * What is the run time?
  * 
  * @return An run time.
  */
 public static int getTime()
 {
   
   return my_time;
 }


  /**
   * Code to test the sorting algorithms.
   * 
   * @param the_args Command line arguments.
   */
  public static void main(final String[] the_args)
  {
    correctnessTest();
    timingTest();
    
    // Note:  Modified timingTest() to assist with data collection testing.    
    
    /*
     * The average run time.
     */
    int average_time = 0;
    
    /*
     * The best average run time. 
     */
    final int[] best_run_time = {0, 0};
    
    
    System.out.println("Correctness Test.");
    correctnessTest();
    
    System.out.println("**************************");
    
    final int[] inputs = {200000, 400000, 800000, 1600000, 3200000};
    final int[] k_values = {2, 3, 5, 10, 20, 50};
    
    for (int k = 0; k < k_values.length; k++) 
    {
      
      System.out.println("Run with k value: " + k_values[k]);
      
      for (int n = 0; n < inputs.length; n++) 
      {
        
        System.out.println("Run with input length: " + inputs[n]);
        
        setK(k_values[k]);
        setN(inputs[n]);
        timingTest();
        
        average_time += getTime();
      }    
      
      average_time = average_time / inputs.length;
      
      if (average_time < best_run_time[0] || best_run_time[0] == 0) 
      {
        
        best_run_time[0] = average_time;
        best_run_time[1] = k;
      }
      
      average_time = 0;
     
      System.out.println("\n\n----------------------------");
    }
    
    System.out.println("Best time: " + best_run_time[0] + " K value: " + best_run_time[1]);
    

  }
}
